#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H

#include <iostream>
#include "dsexceptions.h"
#include <algorithm>
#include <random>
#include <iterator>
using namespace std;       

/// BinarySearchTree class
///
/// CONSTRUCTION: zero parameter
///
/// ******************PUBLIC OPERATIONS*********************
/// void insert( x )       --> Insert x
/// void remove( x )       --> Remove x
/// bool contains( x )     --> Return true if x is present
/// Comparable findMin( )  --> Return smallest item
/// Comparable findMax( )  --> Return largest item
/// boolean isEmpty( )     --> Return true if empty; else false
/// void makeEmpty( )      --> Remove all items
/// void printTree( )      --> Print tree in sorted order
/// ******************ERRORS********************************
/// Throws UnderflowException as warranted

///在原代码的基础上将struct Node变为由class Node派生而出的BinaryNode
///将原先的t->element和t->left变为t->getElement()和t->getLeft()。

/**
 *@brief 基类Node，可派生出BinaryNode等类
 *存储element，并且提供了获取数据并且设置数据的函数
 */
template <typename Comparable>
class Node
{
 private:
  Comparable element;
 public:
  virtual Comparable getElement() const {return element;}
  virtual void setElement(Comparable _val) {element = _val;}
  Node(Comparable _val) {element = _val;}
};

template <typename Comparable>
class BinarySearchTree
{
  public: 
    BinarySearchTree( ) : root{ nullptr } 
    {}

    /**
     * Copy constructor
     */
    BinarySearchTree( const BinarySearchTree & rhs ) : root{ nullptr }
    {
		root = clone( rhs.root );
    }
    
    /**
     * Destructor for the tree
     */
    ~BinarySearchTree( )
    {
        makeEmpty( );
    }

    /**
     * Copy assignment
     */
    BinarySearchTree & operator=( const BinarySearchTree & rhs )
    {
        BinarySearchTree copy = rhs;
        std::swap( *this, copy );
        return *this;
    }
    
    /**
     * Find the smallest item in the tree.
     * Throw UnderflowException if empty.
     */
    const Comparable & findMin( ) const
    {
        if( isEmpty( ) )
            throw UnderflowException{ };
        return findMin( root )->getElement();
    }

    /**
     * Find the largest item in the tree.
     * Throw UnderflowException if empty.
     */
    const Comparable & findMax( ) const
    {
        if( isEmpty( ) )
            throw UnderflowException{ };
        return findMax( root )->getElement();
    }

    /**
     * Returns true if x is found in the tree.
     */
    bool contains( const Comparable & x ) const
    {
        return contains( x, root );
    }

    /**
     * Test if the tree is logically empty.
     * Return true if empty, false otherwise.
     */
    bool isEmpty( ) const
    {
        return root == nullptr;
    }

    /**
     * Print the tree contents in sorted order.
     */
    void printTree( ostream & out = cout ) const
    {
        if( isEmpty( ) )
            out << "Empty tree" << endl;
        else
            printTree( root, out );
    }

    /**
     * Make the tree logically empty.
     */
    void makeEmpty( )
    {
        makeEmpty( root );
    }

    /**
     * Insert x into the tree; duplicates are ignored.
     */
    void insert( const Comparable & x )
    {
        insert( x, root );
    }
    
    /**
     * Remove x from the tree. Nothing is done if x is not found.
     */
    void remove( const Comparable & x )
    {
        remove( x, root );
    }  
    

  private:
    /**
     *@brief 由Node类派生而出
     *私有部分存储了左、右子树的节点指针，并且在公有部分提供了获取左右子树节点指针的函数
     */
    class BinaryNode : public Node<Comparable>
    {
    private:
      BinaryNode* left;
      BinaryNode* right;
    public:
      BinaryNode* getLeft() const
      {
	return left;
      }
      BinaryNode* getRight() const
      {
	return right;
      }
    BinaryNode(Comparable _val) : Node<Comparable>(_val) {left = nullptr;right = nullptr;}
    };
  BinaryNode* root = nullptr;

  void insert( const Comparable & _val, BinaryNode * t )
  {
    if ( t == nullptr )
      t = new BinaryNode {_val};
    else if ( t->getElement() > _val )
      insert( _val, left );
    else if ( t->getElement() < _val )
      insert( _val, right );
    else;
  }

    /**
     * Internal method to remove from a subtree.
     * x is the item to remove.
     * t is the node that roots the subtree.
     * Set the new root of the subtree.
     */
    void remove( const Comparable & _val, BinaryNode * t )
    {
        if( t == nullptr )
            return; 
        if( _val < t->getElement() )
	  remove( _val, t->getLeft() );
        else if( t->getElement() < _val )
	  remove( _val, t->getRight() );
        else if( t->getLeft() != nullptr && t->getRight() != nullptr ) 
        {
	  t->setElement( findMin( t->getRight() )->getElement() );
	  remove( t->getElement(), t->getRight() );
        }
        else
        {
            BinaryNode *oldNode = t;
            t = ( t->getLeft() != nullptr ) ? t->getLeft() : t->getRight();
            delete oldNode;
        }
    }

    /**
     * Internal method to find the smallest item in a subtree t.
     * Return node containing the smallest item.
     */
    BinaryNode * findMin( BinaryNode *t ) const
    {
        if( t == nullptr )
            return nullptr;
        if( t->getLeft() == nullptr )
            return t;
        return findMin( t->getLeft() );
    }

    /**
     * Internal method to find the largest item in a subtree t.
     * Return node containing the largest item.
     */
    BinaryNode * findMax( BinaryNode *t ) const
    {
        if( t != nullptr )
	  while( t->getRight() != nullptr )
	    t = t->getRight();
        return t;
    }


    /**
     * Internal method to test if an item is in a subtree.
     * x is item to search for.
     * t is the node that roots the subtree.
     */
    bool contains( const Comparable & _val, BinaryNode *t ) const
    {
        if( t == nullptr )
            return false;
        else if( _val < t->getElement() )
	  return contains( _val, t->getLeft() );
        else if( t->getElement() < _val )
	  return contains( _val, t->getRight() );
        else
            return true;
    }

    /**
     * Internal method to make subtree empty.
     */
    void makeEmpty( BinaryNode * t )
    {
        if( t != nullptr )
        {
	  makeEmpty( t->getLeft() );
	  makeEmpty( t->getRight() );
            delete t;
        }
        t = nullptr;
    }

    /**
     * Internal method to print a subtree rooted at t in sorted order.
     */
    void printTree( BinaryNode *t, ostream & out ) const
    {
        if( t != nullptr )
        {
	  printTree( t->getLeft(), out );
	  out << t->getElement() << endl;
	  printTree( t->getRight(), out );
        }
    }
    BinaryNode * clone( BinaryNode *t ) const
    {
        if( t == nullptr )
            return nullptr;
        else
	  return new BinaryNode{ t->getElement() };
    }
};



#endif
